Search for: All records

The VAST Challenges have been shown to be an effective tool in visual analytics education, encouraging student learning while enforcing good visualization design and development practices. However, research has observed that students often struggle at identifying a good "starting point" when tackling the VAST Challenge. Consequently, students who could not identify a good starting point failed at finding the correct solution to the challenge. In this paper, we propose a preliminary guideline for helping students approach the VAST Challenge and identify initial analysis directions. We recruited two students to analyze the VAST 2017 Challenge using a hypothesis-driven approach, where they were required to pre-register their hypotheses prior to inspecting and analyzing the full dataset. From their experience, we developed a prescriptive guideline for other students to tackle VAST Challenges. In a preliminary study, we found that the students were able to use the guideline to generate well-formed hypotheses that could lead them towards solving the challenge. Additionally, the students reported that with the guideline, they felt like they had concrete steps that they could follow, thereby alleviating the burden of identifying a good starting point in their analysis process. 

Waiting at the right location at the right time can be critically important in certain variants of time-dependent shortest path problems. We investigate the computational complexity of time-dependent shortest path problems in which there is either a penalty on waiting or a limit on the total time spent waiting at a given subset of the nodes. We show that some cases are nondeterministic polynomial-time hard, and others can be solved in polynomial time, depending on the choice of the subset of nodes, on whether waiting is penalized or constrained, and on the magnitude of the penalty/waiting limit parameter. Summary of Contributions: This paper addresses simple yet relevant extensions of a fundamental problem in Operations Research: the Shortest Path Problem (SPP). It considers time-dependent variants of SPP, which can account for changing traffic and/or weather conditions. The first variant that is tackled allows for waiting at certain nodes but at a cost. The second variant instead places a limit on the total waiting. Both variants have applications in transportation, e.g., when it is possible to wait at certain locations if the benefits outweigh the costs. The paper investigates these problems using complexity analysis and algorithm design, both tools from the field of computing. Different cases are considered depending on which of the nodes contribute to the waiting cost or waiting limit (all nodes, all nodes except the origin, a subset of nodes…). The computational complexity of all cases is determined, providing complexity proofs for the variants that are NP-Hard and polynomial time algorithms for the variants that are in P.